Christine Task
Chris Clifton
ABSTRACT
Privacy of social network data is a growing concern which threatens to limit access to this valuable data source. Analysis of the graph structure of social networks can provide valuable information for revenue generation and social science research, but unfortunately, ensuring this analysis does not violate individual privacy is difficult. Simply anonymizing graphs or even releasing only aggregate results of analysis may not provide sufficient protection. Differential privacy is an alternative privacy model, popular in data-mining over tabular data, which uses noise to obscure individuals' contributions to aggregate results and offers a very strong mathematical guarantee that individuals' presence in the data-set is hidden. Analyses that were previously vulnerable to identification of individuals and extraction of private data may be safely released under differential-privacy guarantees. We review two existing standards for adapting differential privacy to network data and analyse the feasibility of several common social-network analysis techniques under these standards. Additionally, we propose out-link privacy, a novel standard for differential privacy over network data, and introduce two powerful out-link private algorithms for common network analysis techniques that were infeasible to privatize under previous differential privacy standards.
- A. Narayanan and V. Shmatikov, "Robust de-anonymization of large sparse datasets," in Proceedings of the 2008 IEEE Symposium on Security and Privacy, 2008, pp. 111-125. Google Scholar
- E. Zheleva and L. Getoor, "Privacy in Social Networks: A Survey," in Social Network Data Analytics, Aggarwal, C. C., Ed., 2011, p. 277.Google Scholar
- A. Narayanan and V. Shmatikov, "De-anonymizing social networks," 2009 30th IEEE Symposium on Security and Privacy, vol. 0, no. c, pp. 173-187, 2009. Google Scholar
- C. Dwork, "Differential privacy: A survey of results," in Theory and Applications of Models of Computation, ser. Lecture Notes in Computer Science, M. Agrawal, D. Du, Z. Duan, and A. Li, Eds. Springer Berlin/ Heidelberg, 2008, pp. 1-19. Google Scholar
- M. Hay, V. Rastogi, G. Miklau, and D. Suciu, "Boosting the accuracy of differentially private histograms through consistency," Proc. VLDB Endow., vol. 3, no. 1-2, pp. 1021-1032, Sep. 2010. Google Scholar
- M. Hay, C. Li, G. Miklau, and D. Jensen, "Accurate estimation of the degree distribution of private networks," Data Mining, IEEE International Conference on, pp. 169-178, 2009. Google Scholar
- V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev, "Private analysis of graph structure," Proceedings of the VLDB Endowment, vol. 4, no. 11, 2011.Google Scholar
- P. Marsden, "Network data and measurement," Annual review of sociology, pp. 435-463, 1990.Google Scholar
- D. J. Watts and S. H. Strogatz, "Collective dynamics of "small-world" networks," Nature, vol. 393, no. 6684, pp. 440-442, Jun. 1998.Google ScholarDigital Library
- P. Holland and S. Leinhardt, "Local structure in social networks," Sociological methodology, vol. 7, no. 1, 1976.Google Scholar
- A. Marin and B. Wellman, "Social network analysis: An introduction," Handbook of social network analysis, vol. 22, no. January, 2010.Google Scholar
- M. Newman, "The structure and function of complex networks," SIAM review, pp. 167-256, 2003.Google ScholarDigital Library
- A. Degenne and M. Forsé, Introducing social networks. SAGE Publications Ltd, 1999.Google Scholar
- D. J. Mir and R. N. Wright, "A differentially private graph estimator," in Proceedings of the 2009 IEEE International Conference on Data Mining Workshops. IEEE Computer Society, 2009, pp. 122-129. Google Scholar
- D. Proserpio, S. Goldberg, and F. McSherry, "A workflow for differentially-private graph synthesis," 2012.Google Scholar
- A. Sala, X. Zhao, C. Wilson, H. Zheng, and B. Y. Zhao, "Sharing graphs using differentially private graph models," in Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference. New York, NY, USA: ACM, 2011, pp. 81-98. Google Scholar
- A. Gupta, A. Roth, and J. Ullman, "Iterative constructions and private data release," in TCC, 2012, pp. 339-356. Google Scholar
- J. J. P. III, T. L. Fond, S. Moreno, and J. Neville, "Fast generation of large scale social networks with clustering," CoRR, 2012.Google Scholar
- A. Machanavajjhala, A. Korolova, and A. D. Sarma, "Personalized social recommendations: accurate or private," Proc. VLDB Endow., vol. 4, no. 7, pp. 440-450, Apr. 2011. Google Scholar
Recommendations
A Novel Differential Privacy Approach that Enhances Classification Accuracy
C3S2E '16: Proceedings of the Ninth International C* Conference on Computer Science & Software EngineeringIn the recent past, there has been a tremendous increase of large repositories of data, examples being in healthcare data, consumer data from retailers, and airline passenger data. These data are continually being shared with interested parties, either ...
Sensitive Disclosures under Differential Privacy Guarantees
BIGDATACONGRESS '15: Proceedings of the 2015 IEEE International Congress on Big DataNon-independent reasoning (NIR) refers to learning the information of one record from other records, under the assumption that these records share the same underlying distribution. Accurate NIR could disclose private information of an individual. An ...
A privacy framework: indistinguishable privacy
EDBT '13: Proceedings of the Joint EDBT/ICDT 2013 WorkshopsIn this paper we illustrate a privacy framework named Indistinguishable Privacy. Indistinguishable privacy could be deemed as the formalization of the existing privacy definitions in privacy preserving data publishing as well as secure multi-party ...
Comments